package com.yoshino.leetcode.interview150.hash;

import java.util.*;

class Solution {
    public static void main(String[] args) {
        new Solution().groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
    }

    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] count = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            count[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if (--count[ransomNote.charAt(i)] < 0) {
                return false;
            }
        }
        return true;
    }

    public boolean isIsomorphic(String s, String t) {
        // s -> t
        int[] match1 = new int[128];
        // t -> s
        int[] match2 = new int[128];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (match1[c] == 0) {
                if (match2[t.charAt(i)] != 0) {
                    return false;
                }
                match1[c] = t.charAt(i);
                match2[t.charAt(i)] = c;
            } else {
                if (match1[c] != t.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean wordPattern(String pattern, String s) {
        String[] split = s.split(" ");
        if (split.length != pattern.length()) {
            return false;
        }
        Map<Character, String> match = new HashMap<>();
        Map<String, Character> match2 = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (match.containsKey(c)) {
                if (!match.get(c).equals(split[i])) {
                    return false;
                }
            } else {
                if (match2.containsKey(split[i])) {
                    return false;
                }
                match.put(c, split[i]);
                match2.put(split[i], c);
            }
        }
        return true;
    }

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] count = new int[128];
        for (char c : t.toCharArray()) {
            count[c]++;
        }
        for (char c : s.toCharArray()) {
            if (--count[c] < 0) {
                return false;
            }
        }
        return true;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> res = new HashMap<>();
        for (String str : strs) {
            char[] c = str.toCharArray();
            Arrays.sort(c);
            String cStr = new String(c);
            if (!res.containsKey(cStr)) {
                List<String> temp = new ArrayList<>();
                temp.add(str);
                res.put(cStr, temp);
            } else {
                res.get(cStr).add(str);
            }
        }
        return new ArrayList<>(res.values());
    }

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (indMap.containsKey(target - nums[i])) {
                return new int[]{indMap.get(target - nums[i]), i};
            } else {
                indMap.put(nums[i], i);
            }
        }
        return new int[0];
    }

    public boolean isHappy(int n) {
        // 当出现循环时，就不是了
        Set<Integer> saved = new HashSet<>();
        while (n != 1) {
            if (saved.contains(n)) {
                return false;
            }
            saved.add(n);
            int temp = 0;
            while (n != 0) {
                temp += Math.pow((n % 10), 2);
                n /= 10;
            }
            n = temp;
        }
        return true;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            } else {
                // 将前面的给替换掉，因为是从前往后遍历，只看前面的
                Integer ind = map.get(nums[i]);
                if (i - ind <= k) {
                    return true;
                }
                map.put(nums[i], i);
            }
        }
        return false;
    }

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        for (int num : nums) {
            if (set.remove(num)) {
                int temp = 1, l = num, r = num;
                while (set.remove(--l)) {
                    temp++;
                }
                while (set.remove(++r)) {
                    temp++;
                }
                res = Math.max(res, temp);
            }
        }
        return res;
    }
}